#include <iostream>

void HeapMap(int *a,int n,int index)
{
    int left = 2 *index + 1;
    int right = 2 *index + 2;
    int max = index;
    if(left < n && a[left] > a[max])
    {
        max = left;
    }
    if(right < n && a[right] > a[max])
    {
        max = right;
    }
    if(max != index)
    {
        std::swap(a[max],a[index]);
        HeapMap(a,n,max);
    }

}


void HeapSort(int *a,int n)
{
    for(int i = n/2 - 1;i >= 0;i--)
    {
        HeapMap(a,n,i);
    }
    for(int i = n - 1;i > 0;i--)
    {
        std::swap(a[0],a[i]);
        HeapMap(a,i,0);
    }
}

// //构建一个堆
// void MakeHeap(int *a,int n,int index)//以index为根构建最大堆
// {
//     int left = 2*index + 1;
//     int right = 2*index + 2;
//     int max = index;
//     if(left < n && a[left] > a[max])
//         max = left;
//     if(right < n && a[right] > a[max])
//         max = right;
//     if(max != index)
//     {
//         std::swap(a[max],a[index]);
//         MakeHeap(a,n,max);
//     }
// }

// void HeapSort(int *a,int n)
// {
//     //从第一个非叶子节点开始构建最大堆  n/2 -1
//     for(int i = n/2 - 1;i >= 0;i--)
//     {
//         MakeHeap(a,n,i);
//     }
//     for(int i = n - 1;i > 0;i--)
//     {
//         std::swap(a[0],a[i]);
//         MakeHeap(a,i,0);
//     }
// }

int main()
{

    int a[5] = {5,1,2,6,3};
    HeapSort(a,5);
    for(int i =0;i <5;i++)
        std::cout<<a[i]<<" ";
    std::cout<<std::endl;

    return 0;
}